package com.example.leetcode.linklist;

/**
 * 反转链表
 * 给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。
 * <p>
 * 输入：
 * {1,2,3}
 * <p>
 * 返回值：
 * {3,2,1}
 */
public class ReverseList {

    public static void main(String[] args) {
        ListNode head1 = new ListNode(1);
        ListNode head2 = new ListNode(2);
        ListNode head3 = new ListNode(3);
        head1.next = head2;
        head2.next = head3;

        ListNode listNode = ReverseList2(head1);
        System.out.println(listNode);
    }

    public static ListNode ReverseList2(ListNode head) {
        if (head == null) {
            return null;
        }

        ListNode pre = null;
        ListNode current = head;
        while(current != null) {
            // 保存当前节点的下一节点
            ListNode temp = current.next;
            // 当前节点的下一节点指向pre
            current.next = pre;
            // pre移到current
            pre = current;
            // current移到temp
            current = temp;
        }
        return pre;
    }

    public static ListNode ReverseList(ListNode head) {
        if (head == null) {
            return null;
        }

        // 返回新的链表，构造一个头节点
        ListNode pre = null;
        ListNode current = head;

        while (current != null) {
            ListNode next = current.next;
            current.next = pre;
            pre = current;
            current = next;
        }

        return pre;
    }
}


